% THIS IS SIGPROC-SP.TEX - VERSION 3.1
% WORKS WITH V3.2SP OF ACM_PROC_ARTICLE-SP.CLS
% APRIL 2009
%
% It is an example file showing how to use the 'acm_proc_article-sp.cls' V3.2SP
% LaTeX2e document class file for Conference Proceedings submissions.
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V3.2SP) *DOES NOT* produce:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) Page numbering
% ---------------------------------------------------------------------------------------------------------------
% It is an example which *does* use the .bib file (from which the .bbl file
% is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission,
% you need to 'insert'  your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% Questions regarding SIGS should be sent to
% Adrienne Griscti ---> griscti@acm.org
%
% Questions/suggestions regarding the guidelines, .tex and .cls files, etc. to
% Gerald Murray ---> murray@hq.acm.org
%
% For tracking purposes - this is V3.1SP - APRIL 2009

\documentclass{acm_proc_article-sp}

\usepackage[spanish]{babel}
%\selectlanguage{spanish}
%\usepackage[spanish]{babel} % varias definiciones para el espaol (por ejemplo usa ''ndice'' en lugar de ''Contents'')
\usepackage[latin1]{inputenc} % caracteres especiales (acentos, eess) 


\begin{document}

\title{Control de accesos\titlenote{Informe correspondiente al Trabajo Pr\'actico N\'umero 2}}
%\subtitle{[Extended Abstract]
%\titlenote{A full version of this paper is available as
%\textit{Author's Guide to Preparing ACM SIG Proceedings Using
%\LaTeX$2_\epsilon$\ and BibTeX} at
%\texttt{www.acm.org/eaddress.htm}}}
%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{3} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor
Mat\'ias Sulzberger\\
       \affaddr{Instituto Tecnol\'ogico de Buenos Aires}\\
       \affaddr{Buenos Aires, Argentina}\\
       \email{msulzber@alu.itba.edu.ar}
% 2nd. author
\alignauthor
Pablo Mui\~{n}a\\
       \affaddr{Instituto Tecnol\'ogico de Buenos Aires}\\
       \affaddr{Buenos Aires, Argentina}\\
       \email{pmuina@alu.itba.edu.ar}
% 3rd. author
\alignauthor
Marcos Pianelli\\
       \affaddr{Instituto Tecnol\'ogico de Buenos Aires}\\
       \affaddr{Buenos Aires, Argentina}\\
       \email{mpianelli@alu.itba.edu.ar}
}
\date{19 Mayo 2009}
% Just remember to make sure that the TOTAL number of authors
% is the number that will appear on the first page PLUS the
% number that will appear in the \additionalauthors section.

\maketitle

\begin{abstract}

El objetivo de este documento es explicar las estrategias utilizadas a la hora de obtener la clave de un usuario, la cual no puede
ser le\'ida ya que no se encuentra almacenada en forma plana. Dicha clave nos permitir\'a leer un archivo que se encuentra
cifrado.

\end{abstract}

\terms{Control de Accesos}

\keywords{cifrado, encripci\'on, obtenci\'on de clave, control de accesos, AES, SHA1, CBC} % NOT required for Proceedings

\section{Introducci\'on}

Dado el siguiente escenario: se posee un archivo, llamado \textit{esp\'ia}, cuyo contenido se pretende leer pero se encuentra
encriptado utilizando AES-128-CBC. La clave para poder desencriptar el mismo se obtiene a partir de las claves de distintos
usuarios. Dichas claves se encuentras almacenadas en un archivo, pero no de forma plana, sino que se encuentra dentro de un
vuelco hexadecimal provieniente	de aplicar SHA1 y otras operaciones. Una vez obtenido el contenido del archivo \textit{esp\'ia}
se obtendr\'an 3 n\'umeros que ser\'an utilizados para obtener un mensjae oculto mediante el esquema de secreto compartido
de Shamir.\\
A lo largo de este informe se detallar\'an las estrategias utilizadas para obtener la claves de algunos de los usuarios para
as\'i poder leer el contenido del archivo esp\'ia, para finalmente poder obtener el mensaje oculto mediante el secreto compartido
de Shamir.

\section{Fuerza Bruta}

Resulta natural, dado que se cuenta con un dispositivo de c\'omputo, intentar todas las claves posibles, algoritmo comunmente
denominado \textit{Fuerza Bruta}. La ventaja fundamental de este algoritmo radica en que asegura encontrar la clave.

\subsection{Problemas encontrados}

Dado que la clave de los usuarios es de 8 d\'igitos, y puede contener tanto letras como n\'umeros, el n\'umero de claves
posibles asciende a $36^8$.\\

Supongamos que podemos procesar 10000 claves por segundo, tardar\'iamos
m\'as de 8 a\~{n}os en procesar todas las claves. Claramente este no es un camino a seguir.

\subsection{Aclaraci\'on}

Este m\'etodo no fue implementado, dado que se realiz\'o el an\'alisis mostrado en la secci\'on anterior con anterioridad.

\section{Diccionarios}

La estrategia implementada consiste en la utilizaci\'on de un diccionario. En primera instancia se procede a probar si son
claves las palabras del mismo. Una vez que probamos las palabras, en caso de no haber encontrado la clave, se procede a probar
las palabras con n\'umeros a su izquierda, ejemplo \textit{1hola}, a la derecha, ejemplo \textit{hola1}, o a ambos lados,
\textit{1hola1}. Tambi\'en se prueba con todos los n\'umeros posibles de 4 digitos, y se duplican palabras, 
ejemplo \textit{holahola}.\\
Otro punto a destacar es que, dado que es com\'un que los usuarios coloquen su nombre de usuario como clave, o bien, como parte
de la misma, se procedi\'o a agregar de manera automatizada al diccionario los nombres de usuario que figuren en el archivo
que contiene los usuarios.\\
Esta estrategia se basa en que la gran mayor\'ia de los usuarios utilizan como clave, o como parte de \'esta, palabras del
lenguaje. Con lo cual resulta razonable partir de \'estas para intentar obtener la clave. Adem\'as, dado que no se se necesitaba
obtener la clave de un usuario en particular, sino la de cualquiera, nos bastaba con encontrar la clave m\'as simple.

\section{Soluci\'on encontrada}
\label{solucion}

Una  vez desencriptado el archivo esp\'ia con el usuario y clave \textit{(mdakle,qwerty1)}, o bien, \textit{(jrodri,ssonci1)} 
se obtuvo lo siguiente:

\begin{verbatim}
Cataratas del Iguazu Misiones,(4, 1066, 1721) 
\end{verbatim}

Por otro lado, los grupos 1 y 2 encontraron el siguiente contenido respectivamente:

\begin{verbatim}
Cataratas del Iguazu Misiones,(1, 1534, 1721) 
Cataratas del Iguazu Misiones,(2, 611, 1721) 
\end{verbatim}

El siguiente paso fue obtener el secreto de Shamir, explicado en la secci\'on \ref{shamir}.

\section{Secreto de Shamir}
\label{shamir}

El objetivo es obtener el secreto de shamir dado los datos presentados en la secci\'on \ref{solucion} y que se observan en 
la tabla \ref{table:datos}, obtener la fecha de la reuni\'on.

\begin{table}[ht]
\centering
\begin{tabular}{|c|c|c|}
\hline \textbf{n} & \textbf{umbral} & \textbf{p}\\
\hline 4 & 1534 & 1721\\
\hline 1 & 611 & 1721\\
\hline 2 & 1066 & 1721\\
\hline
\end{tabular}
\caption{Contenido de los archivos esp\'ia}
\label{table:datos}
\end{table}

Para resolverlo se ultiliza el polinomio interpolador de Lagrange para generar un polinomio que pase por los puntos:

\begin{enumerate}
\item (1,1534)
\item (2, 611)
\item (4,1066) 
\end{enumerate}

Obteniedo luego de operar algebraicamente:

%\begin{equation}
%P(x) =  \left( 1534\frac{(x - 2) (x - 4)}{(1-2)(1-4)} + 611\frac{(x - 1)(x - 4)}{(2-1)(2-4)} + 1066\frac{(x - 1)(x - 2)}{(4-1)(4-2)} \right)mod(1721)
%\end{equation}

\begin{equation}
P(x) =  \left(    \frac{13}{2}(496-319x+59x^2)  \right)mod(1721)
\end{equation}

Finalmente evaluando en $0$ obtenemos el secreto compartido:

\begin{equation}
P(0) = (3224)mod(1721) =  1503  
\end{equation}

Por lo que podemos conclu\'ir que la reuni\'on se llevar\'a a cabo en \textbf{Cataratas del Iguazu Misiones, el 15 de Marzo}.

\section{Limitaciones}

Es importante notar que este m\'etodo no asegura encontrar la clave, de hecho, si la clave tiene una gran complejidad y carece
de contenido sem\'antico, como por ejemplo \textit{d8t3jpn7}, el algoritmo no la encontrar\'a.

\section{Posibles extensiones}

Existen m\'ultiples estrategias que se pueden utilizar para lograr obtener la clave de un usuario, pero es importante notar
que conforme aumenta la cantidad de intentos se degrada la performance. Por ende tenemos que ser cautelosos a la hora de la
adopci\'on de una nueva estrategia.

\subsection{Inclusi\'on de diccionarios de m\'ultiples lenguajes}

Ser\'ia interesante incluir diccionarios de m\'ultiples idiomas. As\'i aumentar\'iamos las palabras, con contenido sem\'antico que el programa
procesar\'a. Tener en cuenta, como se dijo previamente, que esto lo m\'as frecuente es que las claves contengan ciertas palabras
de un lenguaje.

\subsection{Inclusi\'on de otros m\'etodos}

Se podr\'ia incluir otros m\'etodos para tratar de descubrir la clave, adem\'as de los ya usados. Por ejemplo, probar
con secuencias de n\'umeros con 2 o m\'as d\'igitos cambiados de orden (por ejemplo, 123465); reemplazar letras de
palabras por n\'umeros que tengan aspecto similar (por ejemplo, h4b10, en lugar de hablo); probar con palabras
escritas de atr\'as hacia adelante (por ejempo, persona: anosrep).

\section{Conclusiones}
\label{conclusiones}

Dada la imposibilidad de probar todo el espacio de claves, existe un juego entre la cantidad de claves con las que se prueba
y la eficiencia. Es por esto que se debe considerar e investigar a la hora de incorporar un nuevo m\'etodo.

%\end{document}  % This is where a 'short' article might terminate

%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\bibliographystyle{abbrv}
\bibliography{InformeTP2}  % sigproc.bib is the name of the Bibliography in this case
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
\end{document}
